package cn.trigram.lang;

import ch.obermuhlner.math.big.DefaultBigDecimalMath;
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.Vector;
import java.util.regex.Pattern;
import java.util.stream.Collectors;
import lombok.Data;
import lombok.SneakyThrows;
import lombok.extern.slf4j.Slf4j;
import org.apache.commons.lang3.StringUtils;

/**
 * 代数表达式计算器工具类，实现加减乘除幂五种混合代数运算表达式
 *
 * @version 1.0.0
 * @date 2022/08/19 16:20:49
 * @since 1.0.0
 */
@Slf4j
public class CalculatorUtil {
    /**
     * 1表示栈内优先级高于栈外优先级，-1表示栈内优先级低于栈外优先级， 0表示优先级相等，需要特别处理，99表示输入错误，符号不匹配或输入字符不可识别。
     * 对于+、-、*、/四个运算符来说，由于运算符的左结合性，相同的符号栈内的优先级高于栈外的优先级；
     * 而幂运算具有右结合性，因此，两个^相比，栈外优先级高于栈内优先级。
     * 对于不同的两个运算符，()中的优先级最高，幂运算高于乘除，乘除高于加减
     */
    private final static int[][] SIGN_PRIORITY = {
            {1, 1, -1, -1, -1, -1, 1, 1, 99},// '+'
            {1, 1, -1, -1, -1, -1, 1, 1, 99},// '-'
            {1, 1, 1, 1, -1, -1, 1, 1, 99},// '*'
            {1, 1, 1, 1, -1, -1, 1, 1, 99},// '/'
            {1, 1, 1, 1, -1, -1, 1, 1, 99},// '^'
            {-1, -1, -1, -1, -1, -1, 0, 99, 99},// '('
            {1, 1, 1, 1, 1, 99, 1, 1, 99},// ')'
            {-1, -1, -1, -1, -1, -1, 99, 0, 99},// '#'
            {99, 99, 99, 99, 99, 99, 99, 99, 99}// invalid
    };

    private static final Pattern COMMA = Pattern.compile(",");

    public static BigDecimal calculator(String expression) {
        if (StringUtils.isBlank(expression)) {
            return null;
        }
        final Queue<Word> infixQueue = lexicalAnalysis(expression);
        log.info("中缀队列：{}", infixQueue.stream().map(word -> "'" + word.text + "'").collect(Collectors.joining(",")));
        final Queue<Word> suffixQueue = infixToSuffix(infixQueue);
        log.info("后缀队列：{}", suffixQueue.stream().map(word -> "'" + word.text + "'").collect(Collectors.joining(",")));
        return calculateSuffix(suffixQueue);
    }

    private static Queue<Word> lexicalAnalysis(String expression) {
        expression = expression + "#";
        final int length = expression.length();
        final char[] chars = expression.toCharArray();
        Queue<Word> lexicalQueue = new LinkedList<>();
        boolean previousSign = true;
        for (int i = 0; i < length; i++) {
            if (
                    ('0' <= chars[i] && chars[i] <= '9') ||
                            ((chars[i] == '-' || chars[i] == '+' || chars[i] == ',' || chars[i] == '.') && previousSign)
            ) {
                previousSign = false;
                StringBuilder builder = new StringBuilder();
                builder.append(chars[i]);
                for (i++; i < length; i++) {
                    if (
                            ('0' <= chars[i] && chars[i] <= '9') ||
                                    (chars[i] == ',' || chars[i] == '.')
                    ) {
                        builder.append(chars[i]);
                    } else {
                        break;
                    }
                }
                lexicalQueue.offer(new Word(true, builder.toString()));
                i--;
            } else if (chars[i] == '-' || chars[i] == '+' || chars[i] == '*' || chars[i] == '/' || chars[i] == '^' || chars[i] == '(' || chars[i] == ')') {
                previousSign = true;
                lexicalQueue.offer(new Word(false, String.valueOf(chars[i])));
            } else if (chars[i] == ' ') {
                continue;
            } else if (chars[i] == '#') {
                break;
            } else {
                throw new IllegalArgumentException("存在['0-9','.+-*/^,()']以外的非法符号[" + chars[i] + "]");
            }
        }
        return lexicalQueue;
    }

    /**
     * 中缀转后缀
     *
     * @param infixQueue
     * @return {@link Vector<Word> }
     */
    private static Queue<Word> infixToSuffix(Queue<Word> infixQueue) {
        Stack<Word> signStack = new Stack<>();
        Queue<Word> suffixQueue = new LinkedList<>();
        Word fst = new Word(false, "#");
        signStack.push(fst);
        for (Word lexical : infixQueue) {
            if (lexical.flag) {
                suffixQueue.offer(lexical);
            } else {
                if (")".equals(lexical.text)) {
                    while (!signStack.empty()) {
                        if ("(".equals(signStack.peek().text)) {
                            signStack.pop();
                            break;
                        }
                        suffixQueue.offer(signStack.pop());
                    }
                } else if (getSignPriority(signStack.peek().text, lexical.text) > 0) {
                    suffixQueue.offer(signStack.pop());
                    signStack.push(lexical);
                } else {
                    signStack.push(lexical);
                }
            }
        }
        while (!signStack.empty()) {
            if (!"#".equals(signStack.peek().text)) {
                suffixQueue.offer(signStack.peek());
            }
            signStack.pop();
        }
        return suffixQueue;
    }


    /**
     * 计算后缀表达式
     *
     * @param suffixQueue
     * @return {@link BigDecimal }
     */
    @SneakyThrows
    private static BigDecimal calculateSuffix(Queue<Word> suffixQueue) {
        Stack<BigDecimal> operandStack = new Stack<>();
        for (Word lexical : suffixQueue) {
            if (lexical.flag) {
                operandStack.push(toBigDecimal(lexical.text));
            } else {
                BigDecimal b = operandStack.pop();
                BigDecimal a = operandStack.pop();
                switch (lexical.text) {
                    case "+":
                        operandStack.push(a.add(b));
                        break;
                    case "-":
                        operandStack.push(a.subtract(b));
                        break;
                    case "*":
                        operandStack.push(a.multiply(b));
                        break;
                    case "/":
                        operandStack.push(a.divide(b, 32, RoundingMode.HALF_UP));
                        break;
                    case "^":
                        try (
                                final DefaultBigDecimalMath.LocalMathContext ignored = DefaultBigDecimalMath.createLocalMathContext(38, RoundingMode.HALF_UP)
                        ) {
                            operandStack.push(DefaultBigDecimalMath.pow(a, b));
                        }
                        break;
                    default:
                        break;
                }
            }
        }
        return operandStack.peek();
    }

    private static int signToArrayIndex(String ch) {
        switch (ch) {
            case "+":
                return 0;
            case "-":
                return 1;
            case "*":
                return 2;
            case "/":
                return 3;
            case "^":
                return 4;
            case "(":
                return 5;
            case ")":
                return 6;
            case "#":
                return 7;
            default:
                return 8;
        }
    }

    /**
     * 比较栈内和栈外的优先级
     *
     * @param inner 栈内部符号
     * @param outer 栈外部符号
     * @return int  优先级
     */
    private static int getSignPriority(String inner, String outer) {

        return SIGN_PRIORITY[signToArrayIndex(inner)][signToArrayIndex(outer)];
    }

    private static BigDecimal toBigDecimal(String val) {
        if (val.contains(",")) {
            return new BigDecimal(COMMA.matcher(val).replaceAll(""));
        }
        return new BigDecimal(val);
    }

    @Data
    private static class Word {
        /**
         * true表示是数值；false表示是允许内的符号
         */
        boolean flag;
        /**
         * 分词
         */
        String text;

        public Word(boolean flag, String text) {
            this.flag = flag;
            this.text = text;
        }
    }
}
